﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace Algoritmia.DataStructures.Sets
{
    public class IntSet : 
        ISet<int>
    {
        private bool[] _array;
        private int _count;
        private int _capacity;

        public IntSet(IEnumerable<int> items = null, int capacity = 0)
        {
            if (items == null)
            {
                items = Enumerable.Empty<int>();
                _capacity = capacity == 0 ? 1 : capacity;
            }
            else
            {
                items = items.ToList();
                _capacity = Math.Max(capacity, ((List<int>)items).Count > 0 ? items.Max() + 1 : -1);
            }

            _array = new bool[_capacity];
            _count = 0;
            foreach (var number in items)
            {
                Add(number);
            }
        }

        public virtual int Capacity 
        {
            get { return _capacity; } 
            set {
                
                Array.Resize( ref _array, value);
                if (value < _capacity)
                {
                    _count = 0;
                    for (var i = 0; i < value; i++)
                        if (_array[i]) _count++;
                }
                _capacity = value;
            } 
        }

        #region ISet<int> members

        public virtual int Count
        {
            get { return _count; }
        }

        public virtual bool Contains(int elem)
        {
            return elem >= 0 && elem < _capacity && _array[elem];
        }

        public virtual void Add(int elem)
        {
            if (elem < 0 || elem >= _capacity)
                throw new ArgumentOutOfRangeException();
            if (!_array[elem])
            {
                _array[elem] = true;
                _count++;
            }
        }

        public virtual void AddUnchecked(int elem)
        {
            _array[elem] = true;
            _count++;
        }

        public virtual void Discard(int elem)
        {
            if (Contains(elem))
            {
                _array[elem] = false;
                _count--;
            }
        }

        public virtual bool Remove(int elem)
        {
            if (!Contains(elem))
                return false;
            _array[elem] = false;
            _count--;
            return true;
        }

        public virtual void Clear()
        {
            for (int i = 0; i < _array.Length; i++)
                _array[i] = false;
            _count = 0;
        }
        #endregion

        #region IEnumerable<T> members

        public virtual IEnumerator<int> GetEnumerator()
        {
            for (int i = 0; i < _array.Length; i++)
                if (_array[i])
                    yield return i;
        }
        #endregion

        #region IEnumerable members

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion

        #region IEquatable<ISet<int>> members

        public virtual bool Equals(ISet<int> other)
        {
            return Count == other.Count && this.IsSuperSetOf(other);            
        }

        #endregion

        public override string ToString()
        {
            return String.Format("{0} {{{1}}} ", GetType().Name, string.Join(",", this));
        }
    }
}
